﻿//编写一个函数来查找字符串数组中的最长公共前缀。
//如果不存在公共前缀，返回空字符串 ""。
//
//输入：strs = ["flower", "flow", "flight"]
//输出："fl"
//
//输入：strs = ["dog", "racecar", "car"]
//输出：""
//解释：输入不存在公共前缀。
//
//提示：
//	1 <= strs.length <= 200
//	0 <= strs[i].length <= 200
//	strs[i] 如果非空，则仅由小写英文字母组成

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // 解法⼀：两两⽐较

        string ret = strs[0];
        for (int i = 1; i < strs.size(); i++)
            ret = findCommon(ret, strs[i]);
        return ret;
    }
    string findCommon(string& s1, string& s2) {
        int i = 0;
        while (i < min(s1.size(), s2.size()) && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }
};